import java.util.*;
//LCR 187. 破冰游戏
class Solution {
    /*
    思路：使用数学方法(先举例)
            你要知道最后的结果是3，带着结果去看问题

        第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
        (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
        第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
        第三次，【1, 3, 4】，本轮要踢出4                                        看1
        第四次，【1, 3】 本轮要踢出1                                            看3
        第五次，【3】
        最后返回3

        我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
        你从第二次，向上看第一次
        你会发现，原来3在0的位置
                现在，3在(0 + 3) % 5
                        => +3 回到上次的位置
                        => %5 防止数组溢出，并且数组本来就是循环数组

        f(n) = ( f(n - 1) + m ) % n
        解释意思：
            f(n) 表示上一次
            f(n - 1) 表示这次，因为我们要从这次回推上一次
            m 表示隔几个
            n表示上一次的数组长度

     */
    public int lastRemaining(int n, int m) {
        int res = 0;// 最后只剩下一位，坐标肯定是0
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}





//力扣107. 二叉树的层序遍历 II
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution1 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        int n=getHeight(root);
        List<List<Integer>> res=new ArrayList<>(n);
        if(root==null){
            return res;
        }
        //预先填充 res，避免 get(n-index) 报错
        for (int i = 0; i < n; i++) {
            res.add(new ArrayList<>());
        }
        func(root,1,res,n);
        return res;
    }
    //index为当前节点的层次，n为该树的深度
    public void func(TreeNode root,int index,List<List<Integer>> res,int n){
        if(root==null){
            return;
        }
        //给该数对应层数的res.add
        res.get(n-index).add(root.val);
        func(root.left,index+1,res,n);
        func(root.right,index+1,res,n);
    }
    //获取树的深度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=getHeight(root.left);
        int right=getHeight(root.right);
        return Math.max(left,right)+1;
    }
}